package com.example.vector;

public class Vector<T> {

    /**
     * 操作               功能                                      适用对象
     * size():          报告向量当前的规模（元素总数）                 向量
     * get(r):          获取秩为 r 的元素                           向量
     * put(r, e):       用 e 替换秩为 r 的元素                      向量
     * insert(r, e):    e 作为秩为 r 的元素插入，原后继元素依次后移      向量
     * remove(r):       删除秩为 r 的元素，返回该元素中原来存放的对象    向量
     * disordered():    判断所有的元素是否已按非降序排列                向量
     * sort():          调整各元素的位置，使之按非降序排列              向量
     * find(e):         查找目标元素 e                              向量
     * search(e):       查找目标元素e,返回不大于 e 且秩最大的元素        有序向量
     * deduplicate():   剔除重复元素                                 向量
     * uniquify():      剔除重复元素                                 有序向量
     * traverse()       遍历向量并统一处理所有元素，处理方法由函数对象指定   向量
     */

    private static final int DEFAULT_CAPACITY = 3; // 默认初始容量

    private int size;
    private int capacity;
    private Object[] elem;

    /**
     * 构造
     */
    public Vector() {
        this.elem = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.capacity = DEFAULT_CAPACITY;
    }

    public Vector(int capacity) {
        this.elem = new Object[this.capacity = capacity];
        this.size = 0;
    }

    public Vector(T[] A, int low, int high) {
        this.copyFrom(A, low, high);
    }

    void copyFrom(T[] A, int low, int high) {
        /**
         * 分配空间
         *      为什么是2倍
         */
        this.elem = new Object[this.capacity = 2 * (high - low)];
        // 规模清零
        this.size = 0;
        // 元素复制
        while (low < high) {
            this.elem[this.size++] = A[low++];
        }
    }

    /**
     * 02B1-2 动态空间管理：向量扩容算法的实现
     * 向量空间不足时扩容，容量加倍
     */
    void expand() {
        if (this.size < this.capacity) return;
        this.capacity = Math.max(this.capacity, DEFAULT_CAPACITY); // 不低于最小容量
        Object[] oldElem = this.elem;
        this.elem = new Object[this.capacity << 1]; // 容量加倍
        for (int i = 0; i < this.size; i++) { // 复制原向量内容
            this.elem[i] = oldElem[i];
        }
    }

    /**
     * 02B1-3.递增式扩容
     * 容量递增策略：每次容量不足时，扩大的容量为一个固定常数，使用这种策略时间复杂度为O(n)
     * 对比加倍扩容的方式：
     *             递增策略        倍增策略
     *   累计时间   O(n^2)          O(n)
     *   分摊回见   O(n)            O（1）
     *   装填因子   约等于100%     大于等于50%
     */


    /**
     * 02B2 分摊复杂度
     * 平均复杂度：根据数据结构各种操作出现概率的分布，将对应的成本加权平均
     *      各种可能的操作，作为独立事件分别考察
     *      割裂了操作之间的相关性和连贯性
     *      往往不能准确的评判数据结构和算法的真实性能
     *
     *  分摊复杂度：对数据结构连续的实施足够多次操作，所需总体成本分摊至单次操作
     *      从实际可行的角度，对一系列操作做整体的考量
     *      更加忠实的刻画了可能出现的操作序列
     *      可以更为精准的评判数据结构和算法的真实性能
     */


    /**
     * 02C1-3.插入
     *
     * @param position 要插入的位置
     * @param e        要插入的元素
     * @return
     */
    public int insert(int position, T e) {
        this.expand(); // 若有必要，扩容
        for (int i = this.size; i > position; i--) {
            this.elem[i] = this.elem[i - 1]; // 将要插入位置的后继依次后移一个单元
        }
        this.elem[position] = e; // 置入新元素
        this.size++; // 更新容量
        return position; // 返回位置
    }

    /**
     * 02C1-4.区间删除
     * 删除区间[lo, hi), 0 <= lo <= hi <= size
     */
    public int remove(int lo, int hi) {
        if (lo == hi) {
            return 0; // 出于效率考虑，单独处理退化的情况
        }
        /**
         * 循环解释：
         *  因为从 lo 这个位置开始，到 hi-1 这个位置的元素都是要删除的
         *  所以，将从 hi 这个位置开始的元素前移 hi-lo 个位置，即将 hi
         *  移到 lo, 将 hi+1 移到 lo+1，以此类推
         */
        while (hi < this.size) {
            this.elem[lo++] = this.elem[hi++]; // [hi, size) 顺次前移hi-lo位
        }
        /**
         * 更新规模，因为在前面的while循环里，lo一直在执行++操作，所以
         * 当元素移动完成的时候，lo的值即为向量最新的规模大小，所以 size = lo
         */
        this.size = lo;
//        shrink(); // 更新规模，若有必要则缩容
        return hi - lo;
    }

    /**
     * 02C1-5.单元素操作
     * 可以将单元素操作视作区间删除操作的特例：[r] = [r, r+1)
     * 删除向量中位置位position的元素，0 <= r < size
     */
    T remove(int position) {
        T e = (T) this.elem[position]; // 备份被删除的元素
        remove(position, position + 1); // 调用区间删除
        return e; // 返回被删除的元素
    }

}
